/**
 * 
 */
package tcss543.cpap.ashish;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

import tcss543.cpap.common.Constants;
import tcss543.cpap.common.ReviewerRank;


/**
 * This is the base class for the GA based solver. It implements the most
 * simplistic naive imlementation. Specialized versions can then override one or
 * more methods.
 * 
 * This one uses a ranked selection.
 * 
 * @author ashish
 * 
 */
public class UniformCrossoverGABasedSolver {

	protected static final double CROSSOVER_PROBABILITY = .90;
	protected static final double MUTATION_PROBABILITY = .05;

	/**
	 * Keep track of the generation
	 */
	protected short generation = 0;
	/**
	 * The max population size.
	 */
	protected static final short POPULATION_SIZE = 50;

	/**
	 * Maximum generations allowed in our solution
	 */
	protected static final short GEN_MAX = 100;
	/**
	 * Represents the current population.
	 */
	protected Chromosome[] population = new Chromosome[POPULATION_SIZE];
	protected final Map<Short, Set<Short>> papers;
	/**
	 * The set of reviewers.
	 */
	protected final Map<Short, Map<Short, ReviewerRank>> reviewers;
	/**
	 * Decides randomly how many reviewers for this paper. Not using a seed on
	 * purpose.
	 */
	protected final Random reviewerCountForPaper = new Random();
	/**
	 * Decides randomly the next reviewer for this paper. No using as seed on
	 * purpose.
	 */
	protected final Random reviewerForPaper = new Random();

	/**
	 * Used to control crossover selection
	 */
	protected final Random selectionController = new Random();

	/**
	 * Used to control crossover selection
	 */
	protected final Random crossoverController = new Random();
	/**
	 * Used to control the mutation
	 */
	protected final Random mutationController = new Random();
	/**
	 * We keep track of the best Chromosome.
	 */
	protected Pair<Chromosome, Short> bestSolSoFar = new Pair<Chromosome, Short>(
			null, null);

	/**
	 * How many generations have seen improvement continguously
	 */
	protected short improvingGenerations = 0;

	/**
	 * Constructor.
	 */
	public UniformCrossoverGABasedSolver(final Map<Short, Set<Short>> p,
			final Map<Short, Map<Short, ReviewerRank>> r) {
		papers = p;
		reviewers = r;
	}

	/**
	 * Responsible for generating the initial population
	 */
	protected void generateInitialPopulation() {
		// generate a random solution for each population
		for (short i = 0; i < population.length; i++) {
			// create and add a solution to population
			population[i] = createARandomChromosome();
		}

		generation += 1;
	}

	/**
	 * @param encoding
	 */
	private Chromosome createARandomChromosome() {
		Map<Short, Set<Short>> encoding = new HashMap<Short, Set<Short>>();

		// for each paper
		for (short p : papers.keySet()) {
			// set to store reviewers assigned to this paper
			TreeSet<Short> r = new TreeSet<Short>();

			// How many reviewers to assign to this paper
			// and which ones?
			short choice = (short) reviewerCountForPaper.nextInt(5);

			short rCountMax;
			switch (choice) {
			case 0:
				rCountMax = Constants.MIN_NUM_OF_REVIEWERS_PER_PAPER;
				break;
			case 1:
				rCountMax = Constants.MIN_NUM_OF_REVIEWERS_PER_PAPER *2;
				break;
			case 2:
				rCountMax = Constants.OPTIMAL_PAPERS_PER_REVIEWER * 3;
				break;
			case 3:
				rCountMax = Constants.OPTIMAL_PAPERS_PER_REVIEWER * 4;
				break;
			case 4:
				rCountMax = Constants.OPTIMAL_PAPERS_PER_REVIEWER * 5;
				break;
			default:
				throw new RuntimeException("No possible!");
			}

			short rCount = 0;
			byte loopCount = 0;
			while (rCount < rCountMax) {
				loopCount++;
				if(loopCount > reviewers.size()){
					//System.out.println("Break out of rmax...");
					break;
				}
				// reviewerid > 0, so add 1
				short rNext = (short) (reviewerForPaper.nextInt(reviewers
						.size()) + 1);
				if (r.add(rNext)) {
					rCount++;
				}
			}

			// add to solution.
			encoding.put(p, r);
		}

		return new Chromosome(encoding, papers, reviewers);

	}

	/**
	 * Responsible for actually generating the next generation. We want to keep
	 * the population to be close POPULATION_SIZE
	 */
	private void generateNextPopulation() {
		selectCandidates();
		generation += 1;
	}

	/**
	 * Encapsulates the selection criteria for selecting candidates to cross
	 * over from current generation.
	 */
	protected void selectCandidates() {
		// The selection criteria in this implementation is to do a rank
		// proportional
		// selection
		// The top 25% have a 60% chance of selection
		// The next 25% have a 20% chance of selection
		// The next 25% have a 15% chance of selection
		// The last have a 5% chance of selection
		Chromosome[] newPopulation = new Chromosome[POPULATION_SIZE];
		// always reintroduce the best so far - Elitism
		newPopulation[0] = bestSolSoFar.fst;
		short count = 1;

		while (count < POPULATION_SIZE) {

			// randomly select parents
			short a = selectIndex();
			short b = selectIndex();

			// generate next chromosome of new population
			Chromosome result = doCrossOver(population[a], population[b]);
			// we get offsprings from doCrossOver

			newPopulation[count] = result;
			// mutation
			doMutations(newPopulation[count]);
			count++;

		}

		// switch the population
		population = newPopulation;
	}

	/**
	 * Returns the index of a current chromosome based on our probability
	 * 
	 * @return
	 */
	protected short selectIndex() {
		double qs = selectionController.nextDouble();

		short start = 0;
		if (qs < 0.60) {
			start = 0;
		} else if (qs < 0.85) {
			start = (short) (0.25 * POPULATION_SIZE);
		} else if (qs < 0.95) {
			start = (short) (0.50 * POPULATION_SIZE);
		} else {
			start = (short) (0.75 * POPULATION_SIZE);
		}

		// generate a number between the start and up to next 25% elements
		return (short) (start + selectionController
				.nextInt((short) (0.25 * POPULATION_SIZE)));
	}

	/**
	 * Encapsulates the strategy to combine two different chromosomes to produce
	 * a single chromosome.
	 * 
	 * @param a
	 *            chromosome a
	 * @param b
	 *            choromosome b
	 * @return 2-4 chromosomes
	 */
	protected Chromosome doCrossOver(Chromosome a, Chromosome b) {
		Chromosome result = a;
		// Parents will reproduce depending on crossover probability
		if (crossoverController.nextDouble() <= CROSSOVER_PROBABILITY) {
			Map<Short, Set<Short>> aEncoding = a.getEncoding();
			Map<Short, Set<Short>> bEncoding = b.getEncoding();
			Map<Short, Set<Short>> childEncoding = new HashMap<Short, Set<Short>>();

			// We use Uniform crossover i.e. randomly copy alleles from both
			// parents.
			for (short p : papers.keySet()) {
				// set to store reviewers assigned to this paper
				childEncoding.put(p, new HashSet<Short>());
				//System.err.println(aEncoding.get(p).size() );
				//System.err.println(bEncoding.get(p).size() );
				boolean firstTime = true;
				outerloop: while (childEncoding.get(p).size() < Constants.MIN_NUM_OF_REVIEWERS_PER_PAPER) {
					for (short rid : aEncoding.get(p)) {
						if (!firstTime
								&& childEncoding.get(p).size() >= Constants.MIN_NUM_OF_REVIEWERS_PER_PAPER) {
							break outerloop;
						}

						if (!firstTime || crossoverController.nextBoolean()) {
							childEncoding.get(p).add(rid);
						}
					}
					for (short rid : bEncoding.get(p)) {
						if (!firstTime
								&& childEncoding.get(p).size() >= Constants.MIN_NUM_OF_REVIEWERS_PER_PAPER) {
							break outerloop;
						}

						if (!firstTime || crossoverController.nextBoolean()) {
							childEncoding.get(p).add(rid);
						}
					}
					firstTime = false;
				}

			}
			result = new Chromosome(childEncoding, papers, reviewers);
		} else if (crossoverController.nextBoolean()) {
			// if no crossover randomly decide if a or b. a is default.
			result = b;
		}

		return result;
	}

	/**
	 * Do a mutation with only an approx MUTATION_PROBABILITY chance. When we do a mutation we
	 * mutate a number of times randomly. Each time we pick a random paper to
	 * mutate and mutate it.
	 * 
	 * @param a
	 *            new mutated or original
	 */
	protected Chromosome doMutations(final Chromosome a) {
		Chromosome result = a;
		if (mutationController.nextDouble() <= MUTATION_PROBABILITY) {

			// mutation count
			short mutationCount = (short) mutationController.nextInt(papers
					.size());
			for (short i = 0; i < mutationCount; i++) {
				Map<Short, Set<Short>> e1 = result.getEncoding();
				short paperToMutate = (short) (mutationController.nextInt(e1
						.size()) + 1);

				// is mutation going to add, or remove a reviewers?
				if (mutationController.nextBoolean()) {
					// add a reviewer not already there
					short rindex = -1;
					while (rindex < 1 || e1.get(paperToMutate).contains(rindex)) {
						rindex = (short) (mutationController.nextInt(reviewers
								.size()) + 1);
					}
					e1.get(paperToMutate).add(rindex);

				} else {
					if (e1.get(paperToMutate).size() > Constants.MIN_NUM_OF_REVIEWERS_PER_PAPER) {
						// remove a reviewer
						short rindex = (short) mutationController.nextInt(e1
								.get(paperToMutate).size());
						e1.get(paperToMutate).remove(rindex);
					}
				}
				result = new Chromosome(e1, papers, reviewers);
				// System.out.println("Mutate");
			}

			/*
			 * if (a.getQuality().compareTo(result.getQuality()) != 0) {
			 * System.out.print("q before m" + a.getQuality());
			 * System.out.println("\tq after m" + result.getQuality()); }
			 */
		}

		return result;
	}

	/**
	 * Also ensures that populations are sorted in descending order.
	 * 
	 * @return
	 */
	public Chromosome solve() {
		generateInitialPopulation();
		Arrays.sort(population);
		bestSolSoFar = new Pair<Chromosome, Short>(population[0], generation);

		while (!isEndingConditionSatisfied()) {
			generateNextPopulation();
			Arrays.sort(population);

			// System.out.println("Generation in solve =" + generation
			// + " best in gen = " + population[0].getQuality());

			if (bestSolSoFar.fst.getQuality().compareTo(
					population[0].getQuality()) < 0) {
				bestSolSoFar = new Pair<Chromosome, Short>(population[0],
						generation);
				// If this was a single improvement after a long time
				// reset to 1
				if (improvingGenerations < 0) {
					improvingGenerations = 1;
				} else {
					// improvement over a previous generation that improved
					// increase
					improvingGenerations++;
				}

			} else {
				if (improvingGenerations > 0) {
					improvingGenerations = -1;
				} else {
					improvingGenerations--;
				}

			}
		}
		/*
		 * System.out.println("Final = " + bestSolSoFar.fst.getQuality() +
		 * " and was found in generation = " + bestSolSoFar.snd +
		 * " out of a total gens of = " + generation);
		 */
		return bestSolSoFar.fst;

	}

	/**
	 * @return true if ending condition met.
	 */
	protected boolean isEndingConditionSatisfied() {
		boolean result = false;
		// stop if Reached GEN_MAX
		// 2. No improvement in last 10 generations
		// 3. ?
		if (generation == GEN_MAX || improvingGenerations < -5) {
			result = true;
		}
		/*
		 * `.println("Gen" + generation + " = " +
		 * bestSolSoFar.getQuality());
		 */
		return result;
	}

}